# 统计所有小于非负整数 n 的质数的数量。

# 示例:

# 输入: 10
# 输出: 4
# 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int

        先将 2~n 的各个数放入表中，然后在2的上面画一个圆圈，然后划去2的其他倍数
        第一个既未画圈又没有被划去的数是3，将它画圈，再划去3的其他倍数；现在既未画圈又没有被划去的第一个数
         是5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于 n 的各数都画了圈或划去为止。这时，
         表中画了圈的以及未划去的那些数正好就是小于 n 的素数。

        list的特性[::i]取i的倍数
        """
        if n < 3:
            return 0
        primes = [True] * n
        primes[0] = primes[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if primes[i]:
                primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
        return sum(primes)

if __name__ == '__main__':
    s = Solution()
    n=10
    print(s.countPrimes(n))

